package complexity;

public class Merge {
    private static Comparable[] assist;
    public static boolean compare(Comparable a,Comparable b){
        return a.compareTo(b)<0;
    }
    public static void exchange(Comparable[] comparable,int a,int b){
        Comparable temp = comparable[a];
        comparable[a]=comparable[b];
        comparable[b]=temp;
    }
    public static void sort(Comparable[] comparable){
        //初始化变量assist
        assist = new Comparable[comparable.length];
        //定义lo和hi变量分别储存数组索引的最大值和最小值
        int lo = 0;
        int hi = comparable.length-1;
        sort(comparable,lo,hi);
    }
    //lo
    public static void sort(Comparable[] comparable,int lo,int hi){
        if (hi<=lo){//7
            return;
        }
        int mid = lo+(hi-lo)/2;
        sort(comparable,lo,mid);//0-3 0-1 0-0  3
        sort(comparable,mid+1,hi);//4-6 6-7  7-7 3
        merge(comparable,lo,mid,hi);
    }
    public static void merge(Comparable[] comparable,int lo,int mid,int hi){
        //定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 =mid+1;
        //遍历移动p1p2指针比较相对应索引处的值找出最小的那个放入辅助数组
        while (p1<=mid&&p2<=hi){
            if (compare(comparable[p1],comparable[p2])){
                assist[i++]=comparable[p1++];
            }else {
                assist[i++]=comparable[p2++];
            }
        }
        //如果p1指针没走完，则顺序移动p1指针将对应元素放入辅助数组
        while (p1<=mid){
            assist[i++]=comparable[p1++];
        }
        //如果p2指针没走完，则顺序移动p2指针将对应元素放入辅助数组
        while (p2<=hi){
            assist[i++]=comparable[p2++];
        }
        //将辅助数组赋值给原数组
        for (int index = lo;index<=hi;index++){
            comparable[index]=assist[index];
        }
    }
}
